《数据结构》考试大纲
一、考查目标
1、掌握数据结构的各类逻辑结构和物理结构的基本概念以及相关操作算法的分析与设计能力；
2、掌握运用数据结构相关知识综合分析问题和解决相关问题的能力。　　
二、考查内容
（一）线性表
1、线性表的定义及其运算；
2、顺序表和链表的定义、组织形式、结构特征和类型说明以及在这两种表上实现的插入、删除和按值查找的算法；
3、循环链表、双向链表的结构特点和在其上实现的插入、删除等操作。
（二）栈和队列
1、栈和队列的定义、特征及在其上所定义的基本运算；
2、在两种存储结构上对栈和队列所施加的基本运算的实现。
（三）树和二叉树
1、树的定义、性质及其存储方法；
2、二叉树的性质；二叉树的二叉链表存储方式、结点结构和类型定义；
3、二叉树的遍历方法及算法；
4、树、森林与二叉树间的相互转换；
5、哈夫曼树的构造方法及应用。
（四）图
1、图的基本概念及术语；图的存储结构(邻接矩阵、邻接表、十字链表)的表示方法；
2、图的遍历(深度优先搜索遍历和广度优先搜索遍历)；图的连通性问题；
3、最小生成树的构造；
4、拓扑排序；
5、关键路径；
6、最短路径。
（五）查找
1、在顺序表、有序表、索引顺序表上的查找方法和算法；
2、二叉排序树、平衡二叉树以及B-树的概念和有关操作；
3、哈希函数的构造方法；处理冲突的方法；
4、各类查找表ASL分析。
（六）内部排序
1、插入排序基本思想、步骤及算法；
2、交换排序基本思想、步骤及算法；
3、选择排序基本思想、步骤及算法；
4、归并排序及基数排序的基本思想、步骤及算法。